package com.yequan.leetcode.tree.minDepth_111;

import com.yequan.leetcode.tree.TreeNode;

/**
 * //给定一个二叉树，找出其最小深度。
 * //
 * // 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * //
 * // 说明: 叶子节点是指没有子节点的节点。
 * //
 * // 示例:
 * //
 * // 给定二叉树 [3,9,20,null,null,15,7],
 * //
 * //     3
 * //   / \
 * //  9  20
 * //    /  \
 * //   15   7
 * //
 * // 返回它的最小深度 2.
 * // Related Topics 树 深度优先搜索 广度优先搜索
 *
 * @author : Administrator
 * @date : 2020/3/29
 */
public class MinDepth {

    public int minDepth(TreeNode root) {
        return helper(root);
    }

    private int helper(TreeNode root) {

        if (null == root) {
            return 0;
        }
        //情况1: 左右孩子都为空,则到达了叶节点,高度1
        if (null == root.left && null == root.right) {
            return 1;
        }
        //情况3: 左右孩子都存在进行递归
        int leftDepth = helper(root.left);
        int rightDepth = helper(root.right);
        //情况2: 左右孩子中有一个为空,则深度为 leftDepth + rightDepth + 1
        if (null == root.left || null == root.right) {
            return leftDepth + rightDepth + 1;
        }
        return Math.min(leftDepth, rightDepth) + 1;

    }

}
